Skip to main content

第46章 二分查找

二分查找(Binary Search)又称折半搜索，是一种高效的查找算法，仅适用于有序序列，核心思路不断折半缩小搜索区间，将线性O(n)O(n)查找优化为对数O(log⁡n)O(\log n)级别。

46.1 二分查找基础原理​

核心前提​

数组/序列必须预先升序或降序排列；仅支持随机访问结构（数组、vector，链表无法高效二分）。

查找逻辑（升序数组）​

  1. 设定左右边界left、right；
  2. 取中间下标mid，对比arr[mid]与目标值target；
  3. 三者情况：
    • 相等：找到目标，返回下标；
    • arr[mid] < target：目标在右半区间，更新left = mid + 1；
    • arr[mid] > target：目标在左半区间，更新right = mid - 1；
  4. 循环直到区间失效（left > right），代表不存在该值。

示例：有序数组[1,3,5,7,9,11,13]查找7 初始区间[0,6]，mid=3，值5 < 7 → 左边界更新为4； 新区间[4,6]，mid=5，值9 >7 → 右边界更新为4； 区间[4,4]，mid=4，值7，匹配成功返回下标4。

46.2 基础二分两种实现​

46.1 迭代实现（推荐，空间O(1)O(1)）​

// 在升序数组arr，长度n，查找target，返回下标；无返回-1
int binarySearchIterative(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        // 避免left+right溢出，替代(left+right)/2
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

46.2 递归实现（空间O(log⁡n)O(\log n)递归栈）​

int binarySearchRecursiveHelper(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        // 搜索右区间
        return binarySearchRecursiveHelper(arr, mid + 1, right, target);
    } else {
        // 搜索左区间
        return binarySearchRecursiveHelper(arr, left, mid - 1, target);
    }
}
// 入口函数
int binarySearchRecursive(int arr[], int n, int target) {
    return binarySearchRecursiveHelper(arr, 0, n - 1, target);
}

46.3 二分查找常用变体（含重复元素）​

46.3.1 查找第一个等于target的下标​

int findFirstOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 向左继续找更早位置
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

46.3.2 查找最后一个等于target的下标​

int findLastOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 向右继续找更晚位置
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

46.3.3 查找target插入位置（不存在返回插入下标）​

int searchInsertPosition(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

46.4 复杂度分析​

  • 时间复杂度：最坏/平均O(log⁡n)O(\log n)，最好O(1)O(1)（mid直接命中）
  • 空间复杂度：迭代O(1)O(1)；递归O(log⁡n)O(\log n)（递归调用栈深度）

46.5 使用前提与注意事项​

  1. 序列必须有序；无序数组无法二分，需先排序（排序O(nlog⁡n)O(n\log n)）；
  2. 避免(left + right) / 2溢出，统一使用left + (right - left) / 2；
  3. 循环条件left <= right不可简写为<，会漏掉边界元素；
  4. 更新边界必须mid±1，否则区间无法收缩，出现死循环；
  5. 降序数组需反转比较逻辑；
  6. 浮点数二分需设置精度阈值判断终止。

46.6 C++标准库二分工具​

<algorithm>内置二分函数，仅适用于升序有序容器：

  1. binary_search(begin, end, val)：返回bool，判断是否存在
  2. lower_bound(begin, end, val)：返回第一个≥val的迭代器
  3. upper_bound(begin, end, val)：返回第一个>val的迭代器

示例代码：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1,3,5,7,7,9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 7;
    bool exist = binary_search(arr, arr + n, target);
    auto itLow = lower_bound(arr, arr + n, target);
    auto itHigh = upper_bound(arr, arr + n, target);
    int idxLow = itLow - arr;
    int idxHigh = itHigh - arr;
    cout << "第一个7下标：" << idxLow << endl;
    cout << "7之后第一个元素下标：" << idxHigh << endl;
    return 0;
}

46.7 二分答案（二分思想拓展）​

核心思想​

不直接查找数组元素，而是二分答案区间，通过check()函数判断当前mid是否满足条件，不断收缩区间求最优解。适用满足单调性的最值类题目。

两类模板​

  1. 求满足条件最大值
// condition(mid)：mid符合条件返回true
int findMax(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (condition(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}
  1. 求满足条件最小值
int findMin(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (condition(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

适用场景​

  • 最大化最小值、最小化最大值；
  • 分段、切割、分配类最优解；
  • 存在单调性的判定类问题。

复杂度​

单次二分O(log⁡答案范围)O(\log\text{答案范围})，总复杂度O(log⁡M×f)O(\log M \times f)，ff为check函数耗时。